题意:
给个液体分组,要求对于任意不同组液体有。求最大的组数,满足组数最大的条件下求每组的最大值的和。有多组询问,每次给定。
首先,?那是啥?
按照题目描述里说的,如果定义表示的整数因式部分,那么
可以看出这玩意也就等于。于是原条件就等价于,考虑用代替原题中的进行计算
另一个问题是求,定义为分解成质因数后最大的指数。
和都可以用线性筛来求,那么我们的线性筛需要筛四个东西
:的最小质因子
:分解成质因数后的指数
:分解成质因数后最大的指数
:的整数因式部分
std::vector<int> pr;
int s[M], h[M], st[M], sm[M];
void prime() {
for (int i = 2; i < M; i++) {
if (!s[i]) { //i是一个质数
pr.push_back(i);
s[i] = i;
st[i] = sm[i] = h[i] = 1;
}
for (int j : pr) { //j是i*j的最小质因子
if (i*j >= M) break;
s[i*j] = j;
st[i*j] = (s[i] == j) ? st[i]+1 : 1;
h[i*j] = (s[i] == j && st[i] & 1) ? h[i]*j : h[i];
sm[i*j] = std::max(sm[i], st[i*j]);
if (i % j == 0) break;
}
}
}
接下来考虑进一步转化问题。刚才我们说,对于任意不同组液体有
再换句话,如果,那么必须在同一组
这样的描述可以转化为图论模型:每种液体是一个节点,如果则节点和之间连一条边。很显然一个连通块内的节点必须在同一组,既然我们要组数最大,那么每个连通块是一组就是最优方案。最大的组数也就是连通块个数,实验得分也很好求,找到每个连通块内最大的然后加起来。
举个例子,当的时候样例大概长这样(点上的数字就是)

于是我们就有了最暴力的算法:对于每个,暴力建图,dfs找连通块,时间复杂度。打上这个应该就可以拿30分。
不过,我们发现,这张图里很多点实际都是没有用的。所有的点就是没有用的,它们都没有连边,都可以单独一组直接计入答案。可以预处理出每个,的点对答案的贡献,这样建图的时候就不用考虑这些点了。
另一方面,对于的点,如果有很多个点的相等,那么这些点都必须在同一组,其中最大的那个可能计入贡献。不妨把它们当作一个点,这个点的就是原来那些点的最大值。
可以考虑按照把所有点分类,由于,那么最多也就只有类,也就是图上最多有个点。而且枚举也只需要枚举到,这个时候建图应该可以AC此题了。代码就不放了。
但是这样复杂度是,并不是最优复杂度,如果的范围是就没了。
可以考虑从开始,从大到小枚举。这样相当于在图上不断加边,连通块可以用并查集维护。具体实现可以在计算完的答案之后,把所有的倍数合并起来。时间复杂度,低于线性复杂度,所以实际上复杂度的瓶颈是线性筛,总体复杂度应该是。
完整代码
#include <cstdio>
#include <vector>
#define N 200000
#define M 20000001
#define R 201
#define L 40001
std::vector<int> pr;
int s[M], h[L]; char st[M], sm[M]; //int改成char极限卡内存
void prime() {
for (int i = 2; i < M; i++) {
if (!s[i]) {
pr.push_back(i);
s[i] = i;
st[i] = sm[i] = 1;
if (i < L) h[i] = 1;
}
for (int j : pr) {
if (i*j >= M) break;
s[i*j] = j;
st[i*j] = (s[i] == j) ? st[i]+1 : 1;
if (i*j < L) h[i*j] = (s[i] == j && st[i] & 1) ? h[i]*j : h[i];
sm[i*j] = std::max(sm[i], st[i*j]);
if (i % j == 0) break;
}
}
}
struct pair {int x, y; };
pair operator + (pair a, pair b) {
return (pair) {a.x + b.x, a.y + b.y};
}
int n, m, a[N], b[N], mv[R], f[R], p[R];
pair co[R], ans[R], cnt;
int fa(int x) {
return x == f[x] ? x : f[x] = fa(f[x]);
}
int main() {
prime();
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++)
scanf("%d", a+i);
for (int i = 0; i < n; i++) {
scanf("%d", b+i);
a[i] = h[a[i]];
b[i] = sm[b[i]];
co[a[i]] = co[a[i]] + (pair) {1, b[i]};
mv[a[i]] = std::max(mv[a[i]], b[i]);
}
for (int i = 2; i < R; i++)
co[i] = co[i] + co[i-1];
for (int i = R-1; i >= 2; i--) {
ans[i] = co[i]+cnt;
if (!mv[i]) continue;
f[i] = i; p[i] = mv[i];
cnt = cnt + (pair) {1, mv[i]};
for (int j = 2; i*j < R; j++) if (mv[i*j]) {
int x = fa(i), y = fa(i*j);
if (x != y) {
f[x] = y;
cnt.x--;
cnt.y -= std::min(p[x], p[y]);
p[y] = std::max(p[x], p[y]);
}
}
}
while (m--) {
int x; scanf("%d", &x);
pair p = (x < R) ? ans[x] : co[R-1];
printf("%d %d\n", p.x, p.y);
}
}